public class Solution11 {
    public int maxArea(int[] height) {
        int res = 0;
        int len = height.length;
        int left, right;
        int first = -1, second = -1;
        for (int i = 0; i < height.length; i++) {
            int i1 = height[i];
            if (first < 0 || i1 > height[first]) {
                second = first;
                first = i;
            } else if (second < 0 || i1 > height[second]) {
                second = i;
            }
        }
        left = Math.min(first, second);
        right = Math.max(first, second);
        int leftMax = left, rightMax = right;
        while (leftMax >= 0 || rightMax < len) {
            while (leftMax >= 0) {
                if (height[leftMax] >= height[left]) {
                    left = leftMax;
                    break;
                }
                leftMax--;
            }
            if (leftMax < 0 && left > 0) {
                left--;
            }
            for (int i = right; i < len; i++) {
                res = Math.max((i - left) * Math.min(height[i], height[left]), res);
            }
            while (rightMax < len) {
                if (height[rightMax] >= height[right]) {
                    right = rightMax;
                    break;
                }
                rightMax++;
            }
            if (rightMax >= len && right < len - 1) {
                right++;
            }
            for (int i = left; i >= 0; i--) {
                res = Math.max((right - i) * Math.min(height[right], height[i]), res);
            }
            leftMax = left - 1;
            rightMax = right + 1;
        }

        return res;
    }

}
